---
title: STL Algorithms
---

The C++ Standard Template Library (STL) provides a rich set of generic algorithms that operate on ranges of elements. These algorithms are designed to be highly efficient and work with various container types through iterators. They offer powerful functionalities for sorting, searching, transforming, and manipulating data, often providing more optimized solutions than manual implementations. This module will compare these algorithms with common JavaScript array methods.

## Algorithm Library Overview

The STL algorithms are typically found in the `<algorithm>` header. They are generic, meaning they work with different data types and container types as long as the iterators provided meet the algorithm's requirements. This separation of algorithms from containers is a key design principle of the STL, promoting reusability and flexibility.

## Sorting Algorithms

Sorting algorithms arrange elements in a specific order.

### `std::sort`

*   Sorts elements in a range in ascending order by default.
*   Typically uses an introsort (hybrid of quicksort, heapsort, and insertion sort) for average O(N log N) complexity.

<UniversalEditor title="Sorting Comparison" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.sort()
let numbers = [5, 2, 8, 1, 9];
numbers.sort((a, b) => a - b); // Sorts in ascending order
console.log(numbers); // [1, 2, 5, 8, 9]

let words = ["banana", "apple", "cherry"];
words.sort(); // Lexicographical sort
console.log(words); // ["apple", "banana", "cherry"]
```

```cpp !! cpp
// C++: std::sort
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <string>

int main() {
  std::vector<int> numbers = {5, 2, 8, 1, 9};
  std::sort(numbers.begin(), numbers.end()); // Sorts in ascending order
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl; // Output: 1 2 5 8 9

  std::vector<std::string> words = {"banana", "apple", "cherry"};
  std::sort(words.begin(), words.end()); // Lexicographical sort
  // for (const std::string& w : words) { std::cout << w << " "; }
  // std::cout << std::endl; // Output: apple banana cherry

  return 0;
}
```
</UniversalEditor>

### `std::stable_sort`

*   Sorts elements while preserving the relative order of equivalent elements.
*   Typically uses merge sort or a similar algorithm, with O(N log N) complexity.

### `std::partial_sort`

*   Sorts only a part of the range, specifically the first `n` elements.

## Searching Algorithms

Searching algorithms find elements within a range.

### `std::find`

*   Searches for the first occurrence of a value in a range.
*   Returns an iterator to the first element that matches, or `last` if not found.
*   Linear search, O(N) complexity.

<UniversalEditor title="Searching Comparison" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.includes(), Array.prototype.indexOf()
let data = [10, 20, 30, 40, 50];

console.log(data.includes(30)); // true
console.log(data.includes(100)); // false

console.log(data.indexOf(20)); // 1
console.log(data.indexOf(99)); // -1
```

```cpp !! cpp
// C++: std::find
#include <iostream>
#include <vector>
#include <algorithm> // For std::find

int main() {
  std::vector<int> data = {10, 20, 30, 40, 50};

  auto it = std::find(data.begin(), data.end(), 30);
  // if (it != data.end()) {
  //   std::cout << "Found 30 at index: " << std::distance(data.begin(), it) << std::endl;
  // } else {
  //   std::cout << "30 not found." << std::endl;
  // }

  it = std::find(data.begin(), data.end(), 100);
  // if (it != data.end()) {
  //   std::cout << "Found 100." << std::endl;
  // } else {
  //   std::cout << "100 not found." << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

### `std::binary_search`

*   Checks if an element exists in a **sorted** range.
*   Returns `true` if found, `false` otherwise.
*   Logarithmic search, O(log N) complexity.

### `std::lower_bound` / `std::upper_bound`

*   `lower_bound`: Returns an iterator to the first element not less than (i.e., greater than or equal to) a given value in a sorted range.
*   `upper_bound`: Returns an iterator to the first element greater than a given value in a sorted range.

## Modifying Algorithms

Modifying algorithms change the elements within a range.

### `std::copy`

*   Copies elements from one range to another.

<UniversalEditor title="Copying Comparison" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.slice(), spread operator
let source = [1, 2, 3];
let destination = [...source]; // Copy using spread
console.log(destination); // [1, 2, 3]

let part = source.slice(0, 2); // Copy a part
console.log(part); // [1, 2]
```

```cpp !! cpp
// C++: std::copy
#include <iostream>
#include <vector>
#include <algorithm> // For std::copy

int main() {
  std::vector<int> source = {1, 2, 3};
  std::vector<int> destination(source.size()); // Pre-allocate space
  std::copy(source.begin(), source.end(), destination.begin());
  // for (int n : destination) { std::cout << n << " "; }
  // std::cout << std::endl; // Output: 1 2 3

  std::vector<int> part(2);
  std::copy(source.begin(), source.begin() + 2, part.begin());
  // for (int n : part) { std::cout << n << " "; }
  // std::cout << std::endl; // Output: 1 2

  return 0;
}
```
</UniversalEditor>

### `std::transform`

*   Applies a function to each element in a range and stores the result in another range.

<UniversalEditor title="Transform Comparison" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.map()
let numbers = [1, 2, 3];
let doubled = numbers.map(num => num * 2);
console.log(doubled); // [2, 4, 6]
```

```cpp !! cpp
// C++: std::transform
#include <iostream>
#include <vector>
#include <algorithm> // For std::transform

int main() {
  std::vector<int> numbers = {1, 2, 3};
  std::vector<int> doubled(numbers.size());

  std::transform(numbers.begin(), numbers.end(), doubled.begin(),
                 [](int num) { return num * 2; }); // Lambda function

  // for (int n : doubled) { std::cout << n << " "; }
  // std::cout << std::endl; // Output: 2 4 6

  return 0;
}
```
</UniversalEditor>

### `std::replace`

*   Replaces all occurrences of a specific value with another value in a range.

## Numeric Algorithms

Numeric algorithms are found in the `<numeric>` header.

### `std::accumulate`

*   Calculates the sum of elements in a range, or applies a binary operation cumulatively.

<UniversalEditor title="Accumulate Comparison" compare={true}>
```javascript !! js
// JavaScript: Array.prototype.reduce()
let numbers = [1, 2, 3, 4, 5];
let sum = numbers.reduce((acc, current) => acc + current, 0);
console.log(sum); // 15
```

```cpp !! cpp
// C++: std::accumulate
#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};
  int sum = std::accumulate(numbers.begin(), numbers.end(), 0); // Initial value 0
  // std::cout << "Sum: " << sum << std::endl; // Output: 15

  return 0;
}
```
</UniversalEditor>

### `std::inner_product`

*   Calculates the inner product of two ranges (sum of products of corresponding elements).

## Comparison with JavaScript Array Methods

JavaScript's `Array.prototype` provides many built-in methods that offer similar functionalities to STL algorithms. However, there are key differences:

| Feature           | JavaScript Array Methods                 | C++ STL Algorithms                       |
| :---------------- | :--------------------------------------- | :--------------------------------------- |
| **Genericity**    | Achieved via dynamic typing              | Achieved via templates and iterators     |
| **Type Safety**   | Runtime type checking                    | Compile-time type checking               |
| **Performance**   | Often optimized internally, but overhead from dynamic typing/GC | Highly optimized, direct memory access, compile-time optimizations |
| **Flexibility**   | Limited to arrays (and array-like objects) | Works with any container that provides iterators |
| **Error Handling**| Throws runtime errors                    | Compile-time errors for type mismatches, runtime errors for invalid iterators |

## Algorithm Performance Analysis

STL algorithms are generally highly optimized and provide strong performance guarantees. Their complexity is often expressed in terms of the number of elements (N) in the range they operate on.

*   **O(N) (Linear):** `std::find`, `std::copy`, `std::transform`, `std::accumulate`.
*   **O(N log N) (Log-linear):** `std::sort`, `std::stable_sort`.
*   **O(log N) (Logarithmic):** `std::binary_search` (on sorted ranges).

Understanding these complexities helps in choosing the most appropriate algorithm for a given task, especially in performance-critical applications.

---

### Practice Questions:
1.  Explain the difference between `std::sort` and `std::stable_sort`. When would you prefer one over the other?
2.  How does `std::transform` in C++ compare to JavaScript's `Array.prototype.map()`? Provide a simple example where you double each element in a vector using `std::transform`.
3.  Discuss the advantages of using STL algorithms over implementing similar functionalities manually in C++.

### Project Idea:
*   Create a C++ program that reads a list of numbers from a file, sorts them, removes duplicates, and then calculates their sum and average. Use appropriate STL containers and algorithms (`std::vector`, `std::sort`, `std::unique`, `std::accumulate`). Compare the performance with a manually implemented version of sorting and summing.
